import java.util.LinkedList;
import java.util.Queue;

class Solution {
    // 1、暴力枚举
//    static int m;
//    static int n;
//
//    public static int numEnclaves(int[][] grid) {
//        m = grid.length;
//        n = grid[0].length;
//        int ret = 0;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                // 满足下标对应的数组值为1，且不是边界下标
//                if (grid[i][j] == 1 && (i != 0 && i != m-1) && (j != 0 && j != n-1)) {
//                    if (!bfs(grid, i, j)) {
//                        ret++;
//                    }
//                }
//            }
//        }
//        return ret;
//    }
//
//    static boolean[][] visited;
//    static int[] dx = {1,-1,0,0};
//    static int[] dy = {0,0,1,-1};
//
//
//    // 在grid数组中，从i、j位置开始遍历，判断是否可以到达边界
//    private static boolean bfs(int[][] grid, int i, int j) {
//        visited = new boolean[m][n];
//        Queue<int[]> queue = new LinkedList<>();
//        queue.offer(new int[]{i,j});
//        visited[i][j] = true;
//        while (!queue.isEmpty()) {
//            int size = queue.size();
//            while (size-- != 0) {
//                int[] arr = queue.poll();
//                for (int k = 0; k < 4; k++) {
//                    int sr = arr[0] + dx[k], sc = arr[1] + dy[k];
//                    if (sr >= 0 && sr < m && sc >= 0 && sc < n && grid[sr][sc] == 1 && !visited[sr][sc]) {
//                        // 如果遇到了边界的话，直接返回true即可
//                        if (sr == 0 || sr == m-1 || sc == 0 || sc == n-1) {
//                            return true;
//                        }
//                        queue.offer(new int[]{sr, sc});
//                        visited[sr][sc] = true;
//                    }
//                }
//            }
//        }
//        return false;
//    }
//
//
//    public static void main(String[] args) {
//        int[][] grid = {
//                {0,0,0,0},
//                {1,0,1,0},
//                {0,1,1,0},
//                {0,0,0,0}
//        };
//        System.out.println(numEnclaves(grid));
//    }


    // 2、单源最短路径优化版
    int m;
    int n;
    boolean[][] visited;

    public int numEnclaves1(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        // 1、将与边界1下标相连的1全部标记为true
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m-1 || j == 0 || j == n-1) && grid[i][j] == 1) {
                    bfs(grid, i, j);
                }
            }
        }
        // 2、统计整个数组中为1，且未被标记的数量
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    ret++;
                }
            }
        }
        return ret;
    }

    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};

    // 标记数组中，与i、j位置相连的1
    private void bfs(int[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        visited[i][j] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                int[] arr = queue.poll();
                for (int k = 0; k < 4; k++) {
                    int sr = arr[0] + dx[k], sc = arr[1] + dy[k];
                    if (sr >= 0 && sr < m && sc >= 0 && sc < n && !visited[sr][sc]) {
                        if (grid[sr][sc] == 1) {
                            queue.offer(new int[]{sr, sc});
                            visited[sr][sc] = true;
                        }
                    }
                }
            }
        }
    }


    // 多源最短路径
    public int numEnclaves2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        // 1、将边界值为1的加入到队列中
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m-1 || j == 0 || j == n-1) && (grid[i][j] == 1)) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        // 2、将与源点相连的1全部标记
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int k = 0; k < 4; k++) {
                int sr = arr[0] + dx[k], sc = arr[1] + dy[k];
                if (sr >= 0 && sr < m && sc >= 0 && sc < n && !visited[sr][sc] && grid[sr][sc] == 1) {
                    queue.offer(new int[]{sr, sc});
                    visited[sr][sc] = true;
                }
            }
        }
        // 3、遍历原始数组，统计未被标记的数量
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    ret++;
                }
            }
        }
        return ret;
    }
}